
public class Day2 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    // 143、重排链表
    public void reorderList(ListNode head) {
        // 处理边界情况
        if(head == null || head.next == null || head.next.next == null) {
            return;
        }

        // 这个题相等于是两个链表进行相加，比如：1->2 和 4->3 这两个链表进行相加，在原链表中呢就是 1->2 和 3->4(进行逆序(头插法))
        // 这个题相当于是分成3步
        // 1、使用快慢指针寻找中间节点
        ListNode slow = head,fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //这个时候slow就是中间节点，slow位置也是第一个链表的尾节点，slow.next是第二个节点的头结点
        // 2、把后面的链表进行逆序
        ListNode head2 = new ListNode(0); // 创建一个哨兵位的头结点
        ListNode cur = slow.next;
        // 这个时候就可以把 slow 指向null了，将其整个链表分成2个
        slow.next = null;
        while(cur != null) {
            ListNode next = cur.next; // 记录当前节点的下一个节点，防止后面逆序之后找不到
            // 进行头插
            cur.next = head2.next;
            head2.next = cur;
            // 进入到下一个节点
            cur = next;
        }
        // 3、合并两个数组
        // 先放head中的链表在放head2中的
        ListNode cur1 = head;
        ListNode cur2 = head2.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(cur1 != null) {
            // 放cur1中的数据
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            if(cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
